package Leetcode;

/*给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
        示例:
        输入: [-2,1,-3,4,-1,2,1,-5,4],
        输出: 6
        解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
        进阶:
        如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。*/


public class problem53 {

    //垃圾算法  veryLaji
    public int maxSubArray(int[] nums) {
        if( nums == null ){
            return 0;
        }
        int l = 0;
        int max = Integer.MIN_VALUE;
        while(l<nums.length){
            int maxResult = Integer.MIN_VALUE;
            int result = 0;
            for(int i = l; i<nums.length;i++){
                result = result+nums[i];
                maxResult = Math.max(maxResult,result);
            }
            max = Math.max(max,maxResult);
            l++;
        }
        return max;
    }


    /***
     * 扫描法,只需要遍历一遍数组 : 如果nums[i]是负数的话,他不可能是代表最优序列的起点
     * 同理得,如果该子序列是负数的话,也不可能是最优子序列的前缀,因此我们可以将 i 一直推到nums[i] > 0
     * 且sum > 0,进行继续的计算.
     * @param nums
     * @return
     */
    public int goodMaxSubArray(int[] nums){
        int max = Integer.MIN_VALUE;
        int sum = 0;

        for(int i = 0; i < nums.length; i++){
            sum += nums[i];

            if(sum > max){
                max = sum;
            }

            if(sum < 0){
                sum = 0;
            }
        }
        return  max;
    }


    /***
     * 递归算法 : 分三种情况
     * 1.二分后,求左半区的最大序列
     * 2.求右半区的最大序列
     * 3.求横跨左右半区的最大序列
     * @param nums
     * @return
     */
    public static int maxSubArray2(int[] nums) {
        return maxSubArrayRec(nums , 0 , nums.length - 1);
    }

    public static int maxSubArrayRec(int[] nums,int left,int right){
        if(left == right){
            return nums[left];
        }

        int mid = left + (right - left)/2;
        int leftMax = maxSubArrayRec(nums , left,mid);
        int rightMax = maxSubArrayRec(nums ,mid + 1,right);
        int leftMaxSum = Integer.MIN_VALUE;
        int temp = 0;

        //必须从中间往两边扩才能算出左右两边相加的最大子序列,如果从左边开始遍历的话可能没有算上mid的数组值
        for(int i = mid;i >= left ; i--){
            temp += nums[i];
            if(temp > leftMaxSum){
                leftMaxSum = temp;
            }
        }

        int rightMaxSum = Integer.MIN_VALUE;
        temp = 0;

        for(int i = mid + 1;i <= right;i++){
            temp += nums[i];
            if(temp > rightMaxSum){
                rightMaxSum = temp;
            }
        }

        return Math.max(Math.max(leftMax,rightMax),leftMaxSum + rightMaxSum);

    }

    public static void main(String[] args) {
        int[] nums = new int[]{-2,-1};
        maxSubArray2(nums);
    }

}
